{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Removals to Make Mountain Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #binary-search #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #二分查找 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumMountainRemovals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得到山形数组的最少删除次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们定义&nbsp;<code>arr</code>&nbsp;是 <b>山形数组</b>&nbsp;当且仅当它满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arr.length &gt;= 3</code></li>\n",
    "\t<li>存在某个下标&nbsp;<code>i</code>&nbsp;（<strong>从 0 开始</strong>）&nbsp;满足&nbsp;<code>0 &lt; i &lt; arr.length - 1</code>&nbsp;且：\n",
    "\t<ul>\n",
    "\t\t<li><code>arr[0] &lt; arr[1] &lt; ... &lt; arr[i - 1] &lt; arr[i]</code></li>\n",
    "\t\t<li><code>arr[i] &gt; arr[i + 1] &gt; ... &gt; arr[arr.length - 1]</code></li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你整数数组&nbsp;<code>nums</code>​ ，请你返回将 <code>nums</code>&nbsp;变成 <strong>山形状数组</strong>&nbsp;的​ <strong>最少</strong>&nbsp;删除次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,3,1]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>数组本身就是山形数组，所以我们不需要删除任何元素。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,1,5,6,2,3,1]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>一种方法是将下标为 0，1 和 5 的元素删除，剩余元素为 [1,5,6,3,1] ，是山形数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>题目保证&nbsp;<code>nums</code> 删除一些元素后一定能得到山形数组。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-removals-to-make-mountain-array](https://leetcode.cn/problems/minimum-number-of-removals-to-make-mountain-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-removals-to-make-mountain-array](https://leetcode.cn/problems/minimum-number-of-removals-to-make-mountain-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,1]', '[2,1,1,5,6,2,3,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0]*(n+1)\n",
    "        for i in range(n):\n",
    "            dp[i] = 1\n",
    "            for j in range(i):\n",
    "                if nums[j]<nums[i]:\n",
    "                    dp[i] = max(dp[i],dp[j]+1)\n",
    "        dp2 = [0]*(n+1)\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp2[i] = 1\n",
    "            for j in range(i+1,n,1):\n",
    "                if nums[j]<nums[i]:\n",
    "                    dp2[i] = max(dp2[i],dp2[j]+1)\n",
    "            if dp[i]>1 and dp2[i]>1:\n",
    "                ans = max(ans,dp[i]+dp2[i]-1)\n",
    "        return n-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0] * n\n",
    "        post = [0] * n\n",
    "        for i in range(1, n):\n",
    "            pre[i] = i\n",
    "            post[n-1-i] = i\n",
    "            for j in range(0, i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    pre[i] = min(pre[i], pre[j] + i - j - 1)\n",
    "                if nums[n-1-i] > nums[n-1-j]:\n",
    "                    post[n-1-i] = min(post[n-1-i], post[n-1-j] + i - j - 1)\n",
    "        #print(pre, post)\n",
    "        return min(pre[i] + post[i] if pre[i] != i and post[i] != n - 1 - i else n for i in range(1, n-1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = [1] * n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    left[i] = max(left[i], left[j] + 1)\n",
    "        \n",
    "        right = [1] * n\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    right[i] = max(right[i], right[j] + 1)\n",
    "\n",
    "        ans = n \n",
    "        for i in range(n):\n",
    "            if right[i] > 1 and left[i] > 1:\n",
    "                ans = min(ans, n - right[i] - left[i] + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for x in range(1,len(nums)-1):\n",
    "            dp = []\n",
    "            for i in nums[:x+1]:\n",
    "                if not dp:\n",
    "                    dp.append(i)\n",
    "                else:\n",
    "                    idx = bisect_left(dp,i)\n",
    "                    if idx == len(dp):\n",
    "                        dp.append(i)\n",
    "                    else:\n",
    "                        dp[idx] = i\n",
    "            if dp[-1] !=nums[x] or len(dp) == 1:\n",
    "                continue\n",
    "            else:\n",
    "                dp1 = []\n",
    "                for i in nums[x:]:\n",
    "                    if not dp1:\n",
    "                        dp1.append(-i)\n",
    "                    else:\n",
    "                        idx = bisect_left(dp1,-i)\n",
    "                        if idx == len(dp1):\n",
    "                            dp1.append(-i)\n",
    "                        else:\n",
    "                            dp1[idx] = -i\n",
    "                if len(dp1) >=2:\n",
    "                    ans = max(ans,len(dp)+len(dp1)-1)\n",
    "        return len(nums) - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        g = []\n",
    "        n = len(nums)\n",
    "        pre = [0]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            idx = bisect_left(g,x)\n",
    "            if idx == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[idx] = x\n",
    "            pre[i] = idx + 1\n",
    "        post = [0]*n\n",
    "        g = []\n",
    "        for i,x in enumerate(nums[::-1]):\n",
    "            idx = bisect_left(g,x)\n",
    "            if idx == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[idx] = x\n",
    "            post[n - 1 - i] = idx + 1\n",
    "\n",
    "        ans = n\n",
    "        for i in range(1,n - 1):\n",
    "            if pre[i] > 1 and post[i] > 1 and n - (post[i] + pre[i] - 1) < ans:\n",
    "                ans = n - (post[i] + pre[i] - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp_min=[1]*n\n",
    "        dp_max=[1]*n\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                if nums[i]>nums[j]:\n",
    "                    dp_max[i]=max(dp_max[i],dp_max[j]+1)\n",
    "        \n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(n-1,i,-1):\n",
    "                if nums[i]>nums[j]:\n",
    "                    dp_min[i]=max(dp_min[i],dp_min[j]+1)\n",
    "        max_len=0\n",
    "        for i in range(1,n-1):\n",
    "            if dp_max[i]>1 and dp_min[i]>1:\n",
    "                max_len=max(max_len,dp_max[i]+dp_min[i]-1)\n",
    "        return n-max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        import math\n",
    "        def binary_search_left(length_min, num):\n",
    "            left = -1\n",
    "            right = len(length_min) - 1\n",
    "            while(left < right):\n",
    "                cur = math.ceil((left + right) / 2)\n",
    "                if length_min[cur] < num:\n",
    "                    left = cur\n",
    "                else:\n",
    "                    right = cur - 1\n",
    "            return left+1\n",
    "\n",
    "        def insert(length_min, length, num):\n",
    "            if length == len(length_min):\n",
    "                length_min.append(num)\n",
    "            else:\n",
    "                length_min[length] = num\n",
    "            return length_min\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        length_minf, length_minb  = [], []\n",
    "        for i in range(n):\n",
    "            #lengthf = bisect_left(length_minf, nums[i])\n",
    "            lengthf = binary_search_left(length_minf, nums[i])\n",
    "            length_minf = insert(length_minf, lengthf, nums[i])\n",
    "            dp[i] += lengthf if lengthf else -n\n",
    "            #lengthb = bisect_left(length_minb, nums[n-1-i])\n",
    "            lengthb = binary_search_left(length_minb, nums[n-1-i])\n",
    "            length_minb = insert(length_minb, lengthb, nums[n-1-i])\n",
    "            dp[n-1-i] += lengthb if lengthb else -n\n",
    "        \n",
    "        return n-max(dp)-1\n",
    "\n",
    "        # n = len(nums)\n",
    "        # dpf = [i for i in range(n)]\n",
    "        # for i in range(1,n):\n",
    "        #     j = i-1\n",
    "        #     while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "        #         j -= 1\n",
    "        # #print(dpf)\n",
    "        # dpb = [i for i in range(n-1,-1,-1)]\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     j = i+1\n",
    "        #     while(j < n and dpb[i] > (j-i-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "        #         j += 1\n",
    "        # #print(dpb)\n",
    "        # res = n\n",
    "        # for i in range(1,n-1):\n",
    "        #     if dpf[i] != i and dpb[i] != n-1-i:\n",
    "        #         res = min(res, dpf[i]+dpb[i])\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        g = []\n",
    "        count1 = []\n",
    "        count2 = []\n",
    "\n",
    "        for x in nums:\n",
    "            j = bisect_left(g, x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "                count1.append(len(g))\n",
    "            else:\n",
    "                g[j] = x\n",
    "                count1.append(j+1)\n",
    "\n",
    "        nums.reverse()\n",
    "        g = []\n",
    "        for x in nums:\n",
    "            j = bisect_left(g, x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "                count2.append(len(g))\n",
    "            else:\n",
    "                g[j] = x\n",
    "                count2.append(j+1)\n",
    "        \n",
    "        count2.reverse()\n",
    "        minnum = 9999999\n",
    "        for i in range(0, len(count1)):\n",
    "            if count1[i] != 1 and count2[i] != 1:\n",
    "                minnum = min((len(nums) - count1[i] - count2[i] + 1), minnum)\n",
    "        \n",
    "        # for x in count1:\n",
    "        #     print(x, end=\" \")\n",
    "        # print()\n",
    "\n",
    "        # for x in count2:\n",
    "        #     print(x, end=\" \")\n",
    "        # print()\n",
    "\n",
    "        return minnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = [0]*n\n",
    "        post = [0]*n\n",
    "        g = []\n",
    "        for i,x in enumerate(nums):\n",
    "            idx = bisect_left(g,x)\n",
    "            if idx == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[idx] = x\n",
    "            pre[i] = idx + 1\n",
    "        g = []\n",
    "        for i,x in enumerate(nums[::-1]):\n",
    "            idx = bisect_left(g,x)\n",
    "            if idx == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[idx] = x\n",
    "            post[n - 1 - i] = idx + 1\n",
    "        \n",
    "        ans = n\n",
    "        for i in range(1,n - 1):\n",
    "            if pre[i] > 1 and post[i] > 1:\n",
    "                ans = min(ans,n - (pre[i] + post[i] - 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = []\n",
    "        pre = [0] * n\n",
    "        for i in range(n):\n",
    "            j = bisect_left(dp, nums[i])\n",
    "            pre[i] = j\n",
    "            if j == len(dp):\n",
    "                dp.append(nums[i])\n",
    "            else:\n",
    "                dp[j] = nums[i]\n",
    "        dp = []\n",
    "        post = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            j = bisect_left(dp, nums[i])\n",
    "            post[i] = j\n",
    "            if j == len(dp):\n",
    "                dp.append(nums[i])\n",
    "            else:\n",
    "                dp[j] = nums[i]\n",
    "        ans = n\n",
    "        for i in range(1, n-1):\n",
    "            if pre[i] and post[i] and n - pre[i] - post[i] - 1 < ans:\n",
    "                ans = n - pre[i] - post[i] - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        up = [0]*n\n",
    "        down = [0]*n\n",
    "        res = 0\n",
    "        rev = nums[::-1]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                if rev[i] > rev[j]:\n",
    "                    down[i] =max(down[i],down[j]+1)\n",
    "                if nums[i] > nums[j]:\n",
    "                    up[i] = max(up[i],up[j]+1)\n",
    "        #print(up,down)\n",
    "        down = down[::-1]\n",
    "        for i in range(len(nums)):\n",
    "            if up[i] == 0 or down[i] == 0:\n",
    "                continue\n",
    "            res = max(res,down[i]+up[i])\n",
    "        return n-res-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        # import math\n",
    "        # def binary_search(length_min, num):\n",
    "        #     if num > length_min[-1]:\n",
    "        #         length_min.append(num)\n",
    "        #         return len(length_min)-1, length_min\n",
    "        #     if num <= length_min[1]:\n",
    "        #         length_min[1] = num\n",
    "        #         return -n, length_min\n",
    "        #     left = 0\n",
    "        #     right = len(length_min) - 1\n",
    "        #     while(left < right):\n",
    "        #         cur = math.ceil((left + right) / 2)\n",
    "        #         if length_min[cur] < num:\n",
    "        #             left = cur\n",
    "        #         else:\n",
    "        #             right = cur - 1\n",
    "        #     length_min[left+1] = num\n",
    "        #     return left+1, length_min\n",
    "\n",
    "        def insert(length_min, length, num):\n",
    "            if length == len(length_min):\n",
    "                length_min.append(num)\n",
    "            else:\n",
    "                length_min[length] = num\n",
    "            return length_min\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        length_minf, length_minb  = [], []\n",
    "        for i in range(n):\n",
    "            lengthf = bisect_left(length_minf, nums[i])\n",
    "            length_minf = insert(length_minf, lengthf, nums[i])\n",
    "            dp[i] += lengthf if lengthf else -n\n",
    "            lengthb = bisect_left(length_minb, nums[n-1-i])\n",
    "            length_minb = insert(length_minb, lengthb, nums[n-1-i])\n",
    "            dp[n-1-i] += lengthb if lengthb else -n\n",
    "        \n",
    "        return n-max(dp)-1\n",
    "\n",
    "        # n = len(nums)\n",
    "        # dpf = [i for i in range(n)]\n",
    "        # for i in range(1,n):\n",
    "        #     j = i-1\n",
    "        #     while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "        #         j -= 1\n",
    "        # #print(dpf)\n",
    "        # dpb = [i for i in range(n-1,-1,-1)]\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     j = i+1\n",
    "        #     while(j < n and dpb[i] > (j-i-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "        #         j += 1\n",
    "        # #print(dpb)\n",
    "        # res = n\n",
    "        # for i in range(1,n-1):\n",
    "        #     if dpf[i] != i and dpb[i] != n-1-i:\n",
    "        #         res = min(res, dpf[i]+dpb[i])\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        g = [] #长度为i的序列的最小障碍\n",
    "        for x in obstacles:\n",
    "            j = bisect_left(g, x) #此处与1964略微不同，相等是不合法的\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "            ans.append(j+1)\n",
    "        return ans\n",
    "    \n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "       #从前到后找最长的，从后到前找最长的。比对两个结果，相加最长的即所需要删除的最短\n",
    "        l = self.longestObstacleCourseAtEachPosition(nums)\n",
    "        r = self.longestObstacleCourseAtEachPosition(nums[::-1])\n",
    "        r = r[::-1]\n",
    "        cur_max = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if l[i] + r[i] > cur_max and l[i] >=2 and r[i] >=2:#特殊情况，由题意，至少长度要为2，否则就是单调增/减\n",
    "                cur_max = l[i]+r[i]\n",
    "        return n- (cur_max-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp_pre=[0]*n\n",
    "        # mn=nums[0]\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if nums[i]>nums[j]:\n",
    "        #             dp_pre[i]=max(dp_pre[i],dp_pre[j]+1)\n",
    "        # #前i个max上坡个数（不包括i）\n",
    "        dp_suf=[0]*n \n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     for j in range(i+1,n):\n",
    "        #         if nums[i]>nums[j]:\n",
    "        #             dp_suf[i]=max(dp_suf[i],dp_suf[j]+1)\n",
    "        # #后i个max上坡数（不包括i）\n",
    "        # ans=n\n",
    "        # print(dp_pre,dp_suf)\n",
    "        # for i in range(1,n-1):\n",
    "        #     if dp_pre[i] and dp_suf[i]:#只有dp_pre[i]和dp_suf[i]都存在方可，左边上坡，右边下坡都要存在数\n",
    "        #         ans=min(ans,n-(dp_pre[i]+dp_suf[i]+1))\n",
    "        # return ans\n",
    "        dp=[]#单调栈\n",
    "        for i,x in enumerate(nums):\n",
    "            j=bisect_left(dp,x)\n",
    "            dp_pre[i]=j\n",
    "            if j==len(dp):\n",
    "                dp.append(x)\n",
    "            else:\n",
    "                dp[j]=x\n",
    "        dp=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x=nums[i]\n",
    "            j=bisect_left(dp,x)\n",
    "            dp_suf[i]=j\n",
    "            if j==len(dp):\n",
    "                dp.append(x)\n",
    "            else:\n",
    "                dp[j]=x\n",
    "        ans=n\n",
    "        for i in range(1,n-1):\n",
    "            if dp_pre[i] and dp_suf[i]:#只有dp_pre[i]和dp_suf[i]都存在方可，左边上坡，右边下坡都要存在数\n",
    "                ans=min(ans,n-(dp_pre[i]+dp_suf[i]+1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dpl=[0]*n\n",
    "        dpr=[0]*n\n",
    "        res=n\n",
    "        for i in range(n):\n",
    "            dpl[i]=i\n",
    "            for j in range(1,i+1):\n",
    "                if nums[i-j]<nums[i]:\n",
    "                    dpl[i]=min(dpl[i],dpl[i-j]+j-1)\n",
    "        for i in range(n):\n",
    "            dpr[n-1-i]=i\n",
    "            for j in range(1,i+1):\n",
    "                if nums[n-1-i+j]<nums[n-1-i]:\n",
    "                    dpr[n-1-i]=min(dpr[n-1-i],dpr[n-1-i+j]+j-1)\n",
    "        for i in range(1,n-1):\n",
    "            if i!=dpl[i] and dpr[i]!=n-1-i:\n",
    "                res=min(res,dpl[i]+dpr[i])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [1] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            for j, y in enumerate(nums[:i]):\n",
    "                if y < x:\n",
    "                    f[i] = max(f[i], f[j] + 1)\n",
    "        g = [1] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n, 1):\n",
    "                if nums[j] < nums[i]:\n",
    "                    g[i] = max(g[i], g[j] + 1)\n",
    "        ans = n\n",
    "        for i in range(1, n):\n",
    "            if f[i] != 1 and g[i] != 1:\n",
    "                ans = min(ans, n - f[i] - g[i] + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "       n = len(nums)\n",
    "       left = [0] * n\n",
    "       _list = []\n",
    "       for i, v in enumerate(nums):\n",
    "          if len(_list) == 0 or _list[-1] < v:\n",
    "             _list.append(v)\n",
    "             left[i] = len(_list)\n",
    "          else:\n",
    "             j = bisect.bisect_left(_list, v)\n",
    "             _list[j] = v\n",
    "             left[i] = j + 1\n",
    "       right = [0] * n\n",
    "       _list.clear()\n",
    "       for i in range(n - 1, -1, -1):\n",
    "          if len(_list) == 0 or _list[-1] < nums[i]:\n",
    "             _list.append(nums[i])\n",
    "             right[i] = len(_list)\n",
    "          else:\n",
    "             j = bisect.bisect_left(_list, nums[i])\n",
    "             _list[j] = nums[i]\n",
    "             right[i] = j + 1\n",
    "       res = n\n",
    "       for i in range(n):\n",
    "          if left[i] != 1 and right[i] != 1:\n",
    "             res = min(res, n - left[i] - right[i] + 1)\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        # f[i] 表示以nums[i]结尾的LIS的长度\n",
    "        # f_r[i] 表示从数组末尾开始的以nums[i]结尾的LIS的长度\n",
    "        # ans[i] = len(nums) - f[i] - f_r[i] + 1\n",
    "        # return min(ans)\n",
    "\n",
    "        # 贪心 + 二分\n",
    "        def LIS(nums):\n",
    "            g = []\n",
    "            ans = []\n",
    "            for x in nums:\n",
    "                j = bisect_left(g, x)\n",
    "                ans.append(j + 1)\n",
    "                if j == len(g):\n",
    "                    g.append(x)\n",
    "                else:\n",
    "                    g[j] = x\n",
    "            return ans\n",
    "        # 递推\n",
    "        # def LIS(nums):\n",
    "        #     f = [0] * len(nums)\n",
    "        #     for i in range(n):\n",
    "        #         for j in range(i):\n",
    "        #             if nums[j] < nums[i]:\n",
    "        #                 f[i] = max(f[i], f[j])\n",
    "        #         f[i] += 1\n",
    "        #     return f\n",
    "\n",
    "        n = len(nums)\n",
    "        f = [0] * n\n",
    "        f_r = [0] * n\n",
    "\n",
    "        f = LIS(nums)\n",
    "        f_r = LIS(nums[::-1])[::-1]\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if f[i] > 1 and f_r[i] > 1:\n",
    "                ans.append(n - f[i] - f_r[i] + 1)\n",
    "        return min(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        import math\n",
    "        def binary_search(length_min, num):\n",
    "            if num > length_min[-1]:\n",
    "                length_min.append(num)\n",
    "                return len(length_min)-1, length_min\n",
    "            if num <= length_min[1]:\n",
    "                length_min[1] = num\n",
    "                return -n, length_min\n",
    "            left = 0\n",
    "            right = len(length_min) - 1\n",
    "            while(left < right):\n",
    "                cur = math.ceil((left + right) / 2)\n",
    "                if length_min[cur] < num:\n",
    "                    left = cur\n",
    "                else:\n",
    "                    right = cur - 1\n",
    "            length_min[left+1] = num\n",
    "            return left+1, length_min\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        length_minf, length_minb  = [0, nums[0]], [0, nums[-1]]\n",
    "        for i in range(1,n-1):\n",
    "            lengthf, length_minf = binary_search(length_minf, nums[i])\n",
    "            dp[i] += lengthf\n",
    "            lengthb, length_minb = binary_search(length_minb, nums[n-1-i])\n",
    "            dp[n-1-i] += lengthb\n",
    "        \n",
    "        return n-max(dp[1:-1])+1\n",
    "\n",
    "        # n = len(nums)\n",
    "        # dpf = [i for i in range(n)]\n",
    "        # for i in range(1,n):\n",
    "        #     j = i-1\n",
    "        #     while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "        #         j -= 1\n",
    "        # #print(dpf)\n",
    "        # dpb = [i for i in range(n-1,-1,-1)]\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     j = i+1\n",
    "        #     while(j < n and dpb[i] > (j-i-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "        #         j += 1\n",
    "        # #print(dpb)\n",
    "        # res = n\n",
    "        # for i in range(1,n-1):\n",
    "        #     if dpf[i] != i and dpb[i] != n-1-i:\n",
    "        #         res = min(res, dpf[i]+dpb[i])\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dpl=[inf]*n\n",
    "        dpr=[inf]*n\n",
    "        dpl[0]=dpr[-1]=0\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                if nums[i]>nums[j]:\n",
    "                    dpl[i]=min(dpl[i],dpl[j]+(i-1-j))\n",
    "            if isinf(dpl[i]):\n",
    "                dpl[i]=i\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i]>nums[j]:\n",
    "                    dpr[i]=min(dpr[i],dpr[j]+(j-1-i))\n",
    "            if isinf(dpr[i]):\n",
    "                dpr[i]=n-i-1\n",
    "        # print(dpl)\n",
    "        # print(dpr)\n",
    "        ans=n-1\n",
    "        for i in range(1,n-1):\n",
    "            lr,rr=dpl[i],dpr[i]\n",
    "            if lr<i and rr<n-i-1:\n",
    "                ans=min(ans,dpl[i]+dpr[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        f = [0] * n\n",
    "        for i,x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    f[i] = max(f[i],f[j])\n",
    "            f[i] += 1\n",
    "        nums2 = nums[::-1]\n",
    "        f2 = [0] * n\n",
    "        for i,x in enumerate(nums2):\n",
    "            for j in range(i):\n",
    "                if nums2[i] > nums2[j]:\n",
    "                    f2[i] = max(f2[i],f2[j])\n",
    "            f2[i] += 1\n",
    "        res = 0\n",
    "        for i in range(1,n-1):\n",
    "            if f[i] > 1 and f2[n-i-1] > 1:\n",
    "                res = max(res, f[i] + f2[n-i-1] - 1)\n",
    "        return n - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        l = [1]*n\n",
    "        for i in range(n-1):\n",
    "            for j in range(i):\n",
    "                if nums[j]<nums[i]:\n",
    "                    l[i] = max(l[i], l[j]+1)\n",
    "        r = [1]*n\n",
    "        for i in range(n-2,0,-1):\n",
    "            for j in range(n-1,i,-1):\n",
    "                if nums[j]<nums[i]:\n",
    "                    r[i] = max(r[i],r[j]+1)\n",
    "        # print(l,r)\n",
    "        ans = n\n",
    "        for i in range(1,n-1):\n",
    "            if l[i]>1 and r[i]>1:\n",
    "                ans = min(n+1-l[i]-r[i],ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        res = len(nums) + 1\r\n",
    "        left = [0] * n \r\n",
    "        st = []\r\n",
    "        for i, x in enumerate(nums):\r\n",
    "            j = bisect_left(st, x)\r\n",
    "            if j == len(st):\r\n",
    "                st.append(x)\r\n",
    "            else:\r\n",
    "                st[j] = x \r\n",
    "            left[i] = j + 1\r\n",
    "        # print(left)\r\n",
    "        st = []\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            x = nums[i]\r\n",
    "            j = bisect_left(st, x)\r\n",
    "            if j == len(st):\r\n",
    "                st.append(x)\r\n",
    "            else:\r\n",
    "                st[j] = x \r\n",
    "            if i and i < n - 1 and left[i] > 1 and j > 0:\r\n",
    "                res = min(res, n - left[i] - j)\r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "\n",
    "        def lengthOfLISInfo(info: List[int]) -> List[int]:\n",
    "            ans = []\n",
    "            g = []\n",
    "            for x in info:\n",
    "                right = bisect_left(g, x)\n",
    "                if right == len(g):\n",
    "                    g.append(x)\n",
    "                    ans.append(len(g))\n",
    "                else:\n",
    "                    g[right] = x\n",
    "                    ans.append(right + 1)\n",
    "            return ans\n",
    "\n",
    "        left = lengthOfLISInfo(nums)\n",
    "\n",
    "        nums.reverse()\n",
    "        right = lengthOfLISInfo(nums)\n",
    "        right.reverse()\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if left[i] == 1 or right[i] == 1:\n",
    "                continue\n",
    "            ans = max(ans, left[i] + right[i])\n",
    "        return n - ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        l_increase=[0]*n\n",
    "        r_increase=[0]*n\n",
    "        p=[]\n",
    "        for i,num in enumerate(nums):\n",
    "            l=0\n",
    "            r=len(p)\n",
    "            while l<r:\n",
    "                mid=l+r>>1\n",
    "                if p[mid]>=num:\n",
    "                    r=mid\n",
    "                else:\n",
    "                    l=mid+1\n",
    "            if r==len(p):\n",
    "                p.append(num)\n",
    "            else:\n",
    "                p[r]=num\n",
    "            l_increase[i]=r+1\n",
    "        p.clear()\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            l=0\n",
    "            r=len(p)\n",
    "            while l<r:\n",
    "                mid=l+r>>1\n",
    "                if p[mid]>=nums[i]:\n",
    "                    r=mid\n",
    "                else:\n",
    "                    l=mid+1\n",
    "            if r==len(p):\n",
    "                p.append(nums[i])\n",
    "            else:\n",
    "                p[r]=nums[i]\n",
    "            r_increase[i]=r+1\n",
    "        ans=inf\n",
    "        for i in range(n):\n",
    "            if l_increase[i]>1 and r_increase[i]>1:\n",
    "                ans=min(ans,n-l_increase[i]-r_increase[i]+1)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        dpl = [1] * len(nums)\n",
    "        dpr = [1] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            for prei in range(0, i):\n",
    "                if nums[prei] < nums[i]:\n",
    "                    dpl[i] = max(dpl[i], dpl[prei]+1)\n",
    "        for i in range(0, len(nums)-1)[::-1]:\n",
    "            for prei in range(i+1, len(nums)):\n",
    "                if nums[prei] < nums[i]:\n",
    "                    dpr[i] = max(dpr[i], dpr[prei]+1)\n",
    "        L = len(nums)\n",
    "        res = L\n",
    "        for i in range(1, len(nums)-1):\n",
    "            if dpl[i] > 1 and dpr[i] > 1:\n",
    "                res = min(res, L-dpl[i]-dpr[i]+1)\n",
    "        # print(dpl)\n",
    "        # print(dpr)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        f = [0] * n\n",
    "        for i,x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                if x > nums[j]:\n",
    "                    f[i] = max(f[i],f[j])\n",
    "            f[i] += 1\n",
    "        nums2 = nums[::-1]\n",
    "        f2 = [0] * n\n",
    "        for i,x in enumerate(nums2):\n",
    "            for j in range(i):\n",
    "                if x > nums2[j]:\n",
    "                    f2[i] = max(f2[i],f2[j])\n",
    "            f2[i] += 1\n",
    "        res = 0\n",
    "        for i in range(1,n-1):\n",
    "            if f[i] > 1 and f2[n-i-1] > 1:\n",
    "                res = max(res, f[i] + f2[n-i-1] - 1)\n",
    "        return n - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        # 最大山形数组，两侧遍历最长递增数组，然后相加\n",
    "\n",
    "        def f1(nums):\n",
    "            dp = [0] * len(nums)\n",
    "            stack = []\n",
    "            for i in range(len(nums)):\n",
    "                item = nums[i]\n",
    "                if not stack or stack[-1] < item:\n",
    "                    stack.append(item)\n",
    "                    dp[i] = len(stack)\n",
    "                else:\n",
    "                    l = 0\n",
    "                    r = len(stack) - 1\n",
    "                    while l < r:\n",
    "                        mid = (l+r)//2\n",
    "                        if stack[mid] < item:\n",
    "                            l = mid + 1 # 最终大于item\n",
    "                        else:\n",
    "                            r = mid\n",
    "                    stack[l] = item\n",
    "                    dp[i] = l + 1\n",
    "            return dp\n",
    "\n",
    "        dp1 = f1(nums)\n",
    "        dp2 = f1(nums[::-1])\n",
    "        dp2.reverse()\n",
    "        count = 0\n",
    "        for i in range(1,len(nums)-1):\n",
    "            if dp1[i] >= 2 and dp2[i] >= 2:\n",
    "                count = max(count,dp1[i] + dp2[i])\n",
    "        return len(nums) - count + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "    #     minDelete = inf\n",
    "    #     def minleft(i,leftdelete):\n",
    "    #         if nums[i-1] >= nums[i]:\n",
    "    #             m = 0\n",
    "    #             for j in range(i-1,-1,-1):\n",
    "    #                 if nums[j] >= nums[i]:\n",
    "    #                     m += 1\n",
    "    #                 else:\n",
    "    #                     return m + leftdelete[j]\n",
    "    #             return m\n",
    "    #         else: \n",
    "    #             min_x = leftdelete[i - 1]\n",
    "    #             for j in range(i-2,-1,-1):\n",
    "    #                 if nums[j] >= nums[i]:\n",
    "    #                     continue\n",
    "    #                 if min_x > leftdelete[j] + i - j - 1:\n",
    "    #                     min_x = leftdelete[j] + i - j - 1\n",
    "    #             return min_x\n",
    "        \n",
    "    #     def minright(i,rightdelete):\n",
    "    #         if nums[i+1] >= nums[i]:\n",
    "    #             m = 0\n",
    "    #             for j in range(i+1,len(nums)):\n",
    "    #                 if nums[j] >= nums[i]:\n",
    "    #                     m += 1\n",
    "    #                 else:\n",
    "    #                     return m + rightdelete[j]\n",
    "    #             return m\n",
    "    #         else: \n",
    "    #             min_x = rightdelete[i+1]\n",
    "    #             for j in range(i+2,len(nums)):\n",
    "    #                 if nums[j] >= nums[i]:\n",
    "    #                     continue\n",
    "    #                 if min_x > rightdelete[j] + j - i - 1:\n",
    "    #                     min_x = rightdelete[j] + j - i - 1\n",
    "    #             return min_x\n",
    "\n",
    "    #     minDelete = inf\n",
    "    #     leftdelete = [inf for i in range(len(nums))]\n",
    "    #     rightdelete = [inf for i in range(len(nums))]\n",
    "    #     leftdelete[0] = 0\n",
    "    #     rightdelete[len(nums)-1] = 0\n",
    "    #     for i in range(1,len(nums)-1):\n",
    "    #         left = minleft(i,leftdelete)\n",
    "    #         leftdelete[i] = left\n",
    "    #     for i in range(len(nums)-2,-1,-1):\n",
    "    #         right = minright(i,rightdelete)\n",
    "    #         rightdelete[i] = right\n",
    "    #     min_i = 0\n",
    "    #     for i in range(1,len(nums)-1):\n",
    "    #         delete = leftdelete[i] + rightdelete[i]\n",
    "    #         if i == leftdelete[i] or len(nums) - i - 1 == rightdelete[i] :\n",
    "    #             continue\n",
    "    #         if minDelete > delete:\n",
    "    #             min_i = i\n",
    "    #             minDelete = delete\n",
    "    #     return minDelete\n",
    "    def minimumMountainRemovals(self,nums):\n",
    "        n = len(nums)\n",
    "        # 最长递增子序列的长度\n",
    "        lis = [1] * n\n",
    "        # 最长递减子序列的长度\n",
    "        lds = [1] * n\n",
    "        \n",
    "        # 计算 lis\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    lis[i] = max(lis[i], lis[j] + 1)\n",
    "        \n",
    "        # 计算 lds\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    lds[i] = max(lds[i], lds[j] + 1)\n",
    "        \n",
    "        # 找到最大的 lis + lds - 1\n",
    "        max_length = 0\n",
    "        for i in range(1, n - 1):\n",
    "            if lis[i] > 1 and lds[i] > 1:  # 保证山顶两边都至少有一个元素\n",
    "                max_length = max(max_length, lis[i] + lds[i] - 1)\n",
    "        \n",
    "        # 总长度减去最大的 lis + lds - 1 即为最小删除次数\n",
    "        return n - max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        max=0\n",
    "        result_left=0\n",
    "        result_right=0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]>nums[max]:\n",
    "                max=i\n",
    "        num_left=nums[:max]\n",
    "        num_right=nums[max+1:]\n",
    "        count_set=[]\n",
    "        for i in range(len(num_left)):\n",
    "            count=0\n",
    "            local_min=i\n",
    "            local_max=i+1\n",
    "            while local_max<len(num_left):\n",
    "                if local_max>local_min:\n",
    "                    local_min =local_max\n",
    "                    local_max=local_max+1\n",
    "                    count=count+1\n",
    "                else:\n",
    "                    local_max=local_max+1\n",
    "            count_set.append(count)\n",
    "        count_set.append(0)\n",
    "        for j in range(len(num_right)):\n",
    "            count=0\n",
    "            local_max=j\n",
    "            local_min=j+1\n",
    "            while local_min<len(num_right):\n",
    "                if local_max> local_min:\n",
    "                    count=count+1\n",
    "                    local_max=local_min\n",
    "                    local_min=local_min+1\n",
    "                else:\n",
    "                    local_min=local_min+1\n",
    "            count_set.append(count)\n",
    "        result_left=count_set[0]\n",
    "        result_right=count_set[max+1]\n",
    "        for i in count_set[:max]:\n",
    "            if i>result_left:\n",
    "                result_left=i\n",
    "        for j in count_set[max+1:]:\n",
    "            if j>result_right:\n",
    "                result_right=j\n",
    "        return len(nums)-result_left-result_right\n",
    "'''\n",
    "\n",
    "        \n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        g = [] #长度为i的序列的最小障碍\n",
    "        for x in obstacles:\n",
    "            j = bisect_left(g,x) #此处与1964略微不同，相等是不合法的\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "            ans.append(j+1)\n",
    "        return ans\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "       #从前到后找最长的，从后到前找最长的。比对两个结果，相加最长的即所需要删除的最短\n",
    "        l = self.longestObstacleCourseAtEachPosition(nums)\n",
    "        r = self.longestObstacleCourseAtEachPosition(nums[::-1])\n",
    "        r = r[::-1]\n",
    "        cur_max = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if l[i] + r[i] > cur_max and l[i] >=2 and r[i] >=2:#特殊情况，由题意，至少长度要为2，否则就是单调增/减\n",
    "                cur_max = l[i]+r[i]\n",
    "        return n- (cur_max-1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        import math\n",
    "        def binary_search(length_min, num):\n",
    "            if num > length_min[-1]:\n",
    "                length_min.append(num)\n",
    "                return len(length_min)-1, length_min\n",
    "            left = 0\n",
    "            right = len(length_min) - 1\n",
    "            while(left < right):\n",
    "                cur = math.ceil((left + right) / 2)\n",
    "                if length_min[cur] < num:\n",
    "                    left = cur\n",
    "                else:\n",
    "                    right = cur - 1\n",
    "            length_min[left+1] = num\n",
    "            return left+1, length_min\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        length_minf, length_minb  = [0], [0]\n",
    "        for i in range(n):\n",
    "            lengthf, length_minf = binary_search(length_minf, nums[i])\n",
    "            dp[i] += lengthf if lengthf != 1 else -n\n",
    "            lengthb, length_minb = binary_search(length_minb, nums[n-1-i])\n",
    "            dp[n-1-i] += lengthb if lengthb != 1 else -n\n",
    "        \n",
    "        return n-max(dp)+1\n",
    "\n",
    "        # n = len(nums)\n",
    "        # dpf = [i for i in range(n)]\n",
    "        # for i in range(1,n):\n",
    "        #     j = i-1\n",
    "        #     while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "        #         j -= 1\n",
    "        # #print(dpf)\n",
    "        # dpb = [i for i in range(n-1,-1,-1)]\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     j = i+1\n",
    "        #     while(j < n and dpb[i] > (j-i-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "        #         j += 1\n",
    "        # #print(dpb)\n",
    "        # res = n\n",
    "        # for i in range(1,n-1):\n",
    "        #     if dpf[i] != i and dpb[i] != n-1-i:\n",
    "        #         res = min(res, dpf[i]+dpb[i])\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        def LIS(nums):\n",
    "            lis, g = [], []\n",
    "            for x in nums:\n",
    "                j = bisect_left(g, x)\n",
    "                lis.append(j+1)\n",
    "                if j == len(g):\n",
    "                    g.append(x)\n",
    "                else:\n",
    "                    g[j] = x\n",
    "            return lis\n",
    "        left = LIS(nums)\n",
    "        right = LIS(nums[::-1])[::-1]\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        for i in range(1, n - 1):\n",
    "            if left[i] > 1 and right[i] > 1:\n",
    "                ans = min(ans, n - left[i] - right[i] + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        front = [1] * N\n",
    "        queue = []\n",
    "        for i, num in enumerate(nums):\n",
    "            idx = bisect.bisect_left(queue, num) if len(queue) else 0\n",
    "            front[i] = idx + 1\n",
    "            if idx == len(queue):\n",
    "                queue.append(num)\n",
    "            else:\n",
    "                queue[idx] = min(queue[idx], num)\n",
    "        ans = 0\n",
    "        queue = []\n",
    "        for i in range(N - 1, -1, -1):\n",
    "            num = nums[i]\n",
    "            idx = bisect.bisect_left(queue, num) if len(queue) else 0\n",
    "            if idx > 0 and front[i] > 1:\n",
    "                ans = max(ans, front[i] + idx)\n",
    "            if idx == len(queue):     \n",
    "                queue.append(num)\n",
    "            else:\n",
    "                queue[idx] = min(queue[idx], num)\n",
    "\n",
    "        return N - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        # import math\n",
    "        # def binary_search(length_min, num):\n",
    "        #     if num > length_min[-1]:\n",
    "        #         length_min.append(num)\n",
    "        #         return len(length_min)-1, length_min\n",
    "        #     if num <= length_min[1]:\n",
    "        #         length_min[1] = num\n",
    "        #         return -n, length_min\n",
    "        #     left = 0\n",
    "        #     right = len(length_min) - 1\n",
    "        #     while(left < right):\n",
    "        #         cur = math.ceil((left + right) / 2)\n",
    "        #         if length_min[cur] < num:\n",
    "        #             left = cur\n",
    "        #         else:\n",
    "        #             right = cur - 1\n",
    "        #     length_min[left+1] = num\n",
    "        #     return left+1, length_min\n",
    "\n",
    "        def insert(length_min, length, num):\n",
    "            if length == len(length_min):\n",
    "                length_min.append(num)\n",
    "            else:\n",
    "                length_min[length] = num\n",
    "            return length_min\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        length_minf, length_minb  = [0, nums[0]], [0, nums[-1]]\n",
    "        for i in range(1,n-1):\n",
    "            #lengthf, length_minf = binary_search(length_minf, nums[i])\n",
    "            lengthf = bisect_left(length_minf, nums[i])\n",
    "            length_minf = insert(length_minf, lengthf, nums[i])\n",
    "            dp[i] += lengthf if lengthf != 1 else -n\n",
    "            #lengthb, length_minb = binary_search(length_minb, nums[n-1-i])\n",
    "            lengthb = bisect_left(length_minb, nums[n-1-i])\n",
    "            length_minb = insert(length_minb, lengthb, nums[n-1-i])\n",
    "            dp[n-1-i] += lengthb if lengthb != 1 else -n\n",
    "        \n",
    "        return n-max(dp[1:-1])+1\n",
    "\n",
    "        # n = len(nums)\n",
    "        # dpf = [i for i in range(n)]\n",
    "        # for i in range(1,n):\n",
    "        #     j = i-1\n",
    "        #     while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "        #         j -= 1\n",
    "        # #print(dpf)\n",
    "        # dpb = [i for i in range(n-1,-1,-1)]\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     j = i+1\n",
    "        #     while(j < n and dpb[i] > (j-i-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "        #         j += 1\n",
    "        # #print(dpb)\n",
    "        # res = n\n",
    "        # for i in range(1,n-1):\n",
    "        #     if dpf[i] != i and dpb[i] != n-1-i:\n",
    "        #         res = min(res, dpf[i]+dpb[i])\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        inc, dec = [], []\n",
    "        finc, fdec = [0] * n, [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            if not inc or num > inc[-1]:\n",
    "                inc.append(num)\n",
    "                finc[i] = len(inc)\n",
    "            else:\n",
    "                pos = bisect_left(inc, num)\n",
    "                inc[pos] = num\n",
    "                finc[i] = pos+1\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = nums[i]\n",
    "            if not dec or num > dec[-1]:\n",
    "                dec.append(num)\n",
    "                fdec[i] = len(dec)\n",
    "            else:\n",
    "                pos = bisect_left(dec, num)\n",
    "                dec[pos] = num\n",
    "                fdec[i] = pos+1\n",
    "\n",
    "        # print(finc, fdec)\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            if finc[i] != 1 and fdec[i] != 1:\n",
    "                ans = max(ans, finc[i]+fdec[i]-1)\n",
    "                # print(f\"{i=} {finc[i]=} {fdec[i]=}\")\n",
    "        \n",
    "        return n-ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        # 以i结尾的最长递增子序列,从左从右分别遍历\n",
    "        n = len(nums)\n",
    "        # 从左往右\n",
    "        q1 = []\n",
    "        left = [1] * n\n",
    "        for i in range(0, n):\n",
    "            num = nums[i]\n",
    "            if not q1 or num > q1[-1]:\n",
    "                q1.append(num)\n",
    "                left[i] = len(q1)\n",
    "            elif num <= q1[-1]:\n",
    "                index = bisect_left(q1, num)\n",
    "                q1[index] = num\n",
    "                left[i] = index + 1\n",
    "        # 从右往左\n",
    "        q2 = []\n",
    "        right = [1] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = nums[i]\n",
    "            if not q2 or num > q2[-1]:\n",
    "                q2.append(num)\n",
    "                right[i] = len(q2)\n",
    "            elif num <= q2[-1]:\n",
    "                index = bisect_left(q2, num)\n",
    "                q2[index] = num\n",
    "                right[i] = index + 1\n",
    "        max_len = 0\n",
    "        for i in range(0, n):\n",
    "            if left[i] != 1 and right[i] != 1:\n",
    "                max_len = max(max_len, left[i] + right[i] - 1)\n",
    "        return n - max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            if nums[i] < nums[i+1]:\n",
    "                break\n",
    "            i += 1\n",
    "        for j in range(n-1,0,-1):\n",
    "            if nums[j] < nums[j-1]:\n",
    "                break\n",
    "            j -= 1\n",
    "        nums = nums[i:j+1]\n",
    "        cut = i+n-1-j\n",
    "        n = len(nums)\n",
    "\n",
    "        dpf = [i for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            j = i-1\n",
    "            while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "                j -= 1\n",
    "        #print(dpf)\n",
    "        dpb = [i for i in range(n-1,-1,-1)]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            j = i+1\n",
    "            while(j < n and dpb[i] > (j-i-1)):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "                j += 1\n",
    "        #print(dpb)\n",
    "        res = n\n",
    "        for i in range(1,n-1):\n",
    "            if dpf[i] != i and dpb[i] != n-1-i:\n",
    "                res = min(res, dpf[i]+dpb[i])\n",
    "        res += cut\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = []\n",
    "        g = []\n",
    "        for x in nums:\n",
    "            i = bisect_left(g, x)\n",
    "            if i == len(g):\n",
    "                g.append(x)\n",
    "                prefix.append(len(g))\n",
    "            else:\n",
    "                g[i] = x\n",
    "                prefix.append(i + 1)\n",
    "        g = []\n",
    "        suffix = []\n",
    "        for x in nums[::-1]:\n",
    "            i = bisect_left(g, x)\n",
    "            if i == len(g):\n",
    "                g.append(x)\n",
    "                suffix.append(len(g))\n",
    "            else:\n",
    "                g[i] = x\n",
    "                suffix.append(i + 1)\n",
    "        suffix = suffix[::-1]\n",
    "        return n - max(prefix[i] + suffix[i] if prefix[i] > 1 and suffix[i] > 1 else -1 for i in range(n)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "\n",
    "        f = [0 for e in nums]\n",
    "        b = [0 for e in nums]\n",
    "\n",
    "        f[0] = 1\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(n):\n",
    "            now = 0\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i] and now < f[j]:\n",
    "                    now = f[j]\n",
    "            f[i] = now + 1\n",
    "        ans = n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            now = 0\n",
    "            for j in range(n-1,i,-1):\n",
    "                if nums[j] < nums[i] and now < b[j]:\n",
    "                    now = b[j]\n",
    "            b[i] = now + 1\n",
    "            if b[i] > 1 and f[i] > 1:\n",
    "                ans = min(ans, n-f[i]-b[i] + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        # import math\n",
    "        # def binary_search(length_min, num):\n",
    "        #     if num > length_min[-1]:\n",
    "        #         length_min.append(num)\n",
    "        #         return len(length_min)-1, length_min\n",
    "        #     if num <= length_min[1]:\n",
    "        #         length_min[1] = num\n",
    "        #         return -n, length_min\n",
    "        #     left = 0\n",
    "        #     right = len(length_min) - 1\n",
    "        #     while(left < right):\n",
    "        #         cur = math.ceil((left + right) / 2)\n",
    "        #         if length_min[cur] < num:\n",
    "        #             left = cur\n",
    "        #         else:\n",
    "        #             right = cur - 1\n",
    "        #     length_min[left+1] = num\n",
    "        #     return left+1, length_min\n",
    "\n",
    "        def insert(length_min, length, num):\n",
    "            if length == len(length_min):\n",
    "                length_min.append(num)\n",
    "            else:\n",
    "                length_min[length] = num\n",
    "            return length_min\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        length_minf, length_minb  = [], []\n",
    "        for i in range(n):\n",
    "            lengthf = bisect_left(length_minf, nums[i])\n",
    "            length_minf = insert(length_minf, lengthf, nums[i])\n",
    "            dp[i] += lengthf if lengthf != 0 else -n\n",
    "            lengthb = bisect_left(length_minb, nums[n-1-i])\n",
    "            length_minb = insert(length_minb, lengthb, nums[n-1-i])\n",
    "            dp[n-1-i] += lengthb if lengthb != 0 else -n\n",
    "        \n",
    "        return n-max(dp[1:-1])-1\n",
    "\n",
    "        # n = len(nums)\n",
    "        # dpf = [i for i in range(n)]\n",
    "        # for i in range(1,n):\n",
    "        #     j = i-1\n",
    "        #     while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "        #         j -= 1\n",
    "        # #print(dpf)\n",
    "        # dpb = [i for i in range(n-1,-1,-1)]\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     j = i+1\n",
    "        #     while(j < n and dpb[i] > (j-i-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "        #         j += 1\n",
    "        # #print(dpb)\n",
    "        # res = n\n",
    "        # for i in range(1,n-1):\n",
    "        #     if dpf[i] != i and dpb[i] != n-1-i:\n",
    "        #         res = min(res, dpf[i]+dpb[i])\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # 前面的最大长度\n",
    "        dp1 = [0] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i] and dp1[j] + 1 > dp1[i]:\n",
    "                    dp1[i] = dp1[j] + 1\n",
    "\n",
    "        # 后面的最大长度\n",
    "        dp2 = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[j] < nums[i] and dp2[j] + 1 > dp2[i]:\n",
    "                    dp2[i] = dp2[j] + 1\n",
    "\n",
    "        ans = n\n",
    "        # 遍历山峰点\n",
    "        for i in range(1, n - 1):\n",
    "            if dp1[i] and dp2[i] and n - dp2[i] - dp1[i] - 1 < ans:\n",
    "                ans = n - dp2[i] - dp1[i] - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        # f[i] 表示以nums[i]结尾的LIS的长度\n",
    "        # f_r[i] 表示从数组末尾开始的以nums[i]结尾的LIS的长度\n",
    "        # ans[i] = len(nums) - f[i] - f_r[i] + 1\n",
    "        # return min(ans)\n",
    "\n",
    "        # 递推\n",
    "        n = len(nums)\n",
    "        f = [0] * n\n",
    "        f_r = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    f[i] = max(f[i], f[j])\n",
    "            f[i] += 1\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for k in range(n - 1, i, -1):\n",
    "                if nums[k] < nums[i]:\n",
    "                    f_r[i] = max(f_r[i], f_r[k])\n",
    "            f_r[i] += 1\n",
    "        \n",
    "        ans = []\n",
    "\n",
    "        for i in range(1, n - 1):\n",
    "            if f[i] > 1 and f_r[i] > 1:\n",
    "                ans.append(n - f[i] - f_r[i] + 1)\n",
    "        return min(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [1] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            for j, y in enumerate(nums[:i]):\n",
    "                if y < x:\n",
    "                    f[i] = max(f[i], f[j] + 1)\n",
    "        g = [1] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if nums[j] < nums[i]:\n",
    "                    g[i] = max(g[i], g[j] + 1)\n",
    "        ans = n\n",
    "        for i in range(1, n):\n",
    "            if f[i] != 1 and g[i] != 1:\n",
    "                ans = min(ans, n - f[i] - g[i] + 1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        # 枚举山峰\n",
    "        n = len(nums)\n",
    "        up_len,down_len = [0]*n,[0]*n\n",
    "        up_len[0],down_len[n-1] = 1,1\n",
    "        for i in range(1,n):\n",
    "            up_len[i] = 1\n",
    "            for j in range(i):\n",
    "                if nums[j]<nums[i]:\n",
    "                    up_len[i] = max(up_len[i], 1+up_len[j])\n",
    "            down_len[n-i-1] = 1\n",
    "            for j in range(n-i,n):\n",
    "                if nums[j]<nums[n-i-1]:\n",
    "                    down_len[n-i-1] = max(down_len[n-i-1], 1+down_len[j])\n",
    "            pass\n",
    "\n",
    "        min_res = float('inf')\n",
    "        for i in range(1,n-1):\n",
    "            cur_cnt = 0\n",
    "            peek = nums[i]\n",
    "            max_left_up_len = 0\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if nums[j] < peek:\n",
    "                    max_left_up_len = max(max_left_up_len, up_len[j])\n",
    "            max_right_down_len = 0\n",
    "            for j in range(i+1, n, 1):\n",
    "                if nums[j] < peek:\n",
    "                    max_right_down_len = max(max_right_down_len, down_len[j])\n",
    "            if max_left_up_len==0 or max_right_down_len==0:\n",
    "                continue\n",
    "            left_rm = i-max_left_up_len\n",
    "            right_rm = n-i-1-max_right_down_len\n",
    "            cur_cnt = left_rm + right_rm\n",
    "            min_res = min(min_res, cur_cnt)\n",
    "        return min_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            if nums[i] < nums[i+1]:\n",
    "                break\n",
    "            i += 1\n",
    "        for j in range(n-1,0,-1):\n",
    "            if nums[j] < nums[j-1]:\n",
    "                break\n",
    "            j -= 1\n",
    "        nums = nums[i:j+1]\n",
    "        cut = i+n-1-j\n",
    "        n = len(nums)\n",
    "\n",
    "        dpf = [i for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            j = i-1\n",
    "            while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "                j -= 1\n",
    "        #print(dpf)\n",
    "        dpb = [i for i in range(n-1,-1,-1)]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            j = i+1\n",
    "            while(j < n and dpb[i] > (j-i-1)):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "                j += 1\n",
    "        #print(dpb)\n",
    "        res = n\n",
    "        for i in range(1,n-1):\n",
    "            if dpf[i] != i and dpb[i] != n-1-i:\n",
    "                res = min(res, dpf[i]+dpb[i])\n",
    "        res += cut\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dpl,dpr=list(range(n)),list(range(n-1,-1,-1))\n",
    "        for i in range(1,n):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if nums[j]<nums[i]:\n",
    "                    dpl[i]=min(dpl[i],dpl[j]+i-j-1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[j]<nums[i]:\n",
    "                    dpr[i]=min(dpr[i],dpr[j]+j-i-1)\n",
    "        ans=inf\n",
    "        for i in range(1,n-1):\n",
    "            if dpl[i]<i and dpr[i]<(n-1-i):\n",
    "                ans=min(ans,dpl[i]+dpr[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "\n",
    "        f = [0 for e in nums]\n",
    "        b = [0 for e in nums]\n",
    "\n",
    "        f[0] = 1\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(n):\n",
    "            now = 0\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i] and now < f[j]:\n",
    "                    now = f[j]\n",
    "            f[i] = now + 1\n",
    "        ans = n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            now = 0\n",
    "            for j in range(n-1,i,-1):\n",
    "                if nums[j] < nums[i] and now < b[j]:\n",
    "                    now = b[j]\n",
    "            b[i] = now + 1\n",
    "            if b[i] > 1 and f[i] > 1:\n",
    "                ans = min(ans, n-f[i]-b[i] + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def LIS(self, nums):\n",
    "        g = []\n",
    "        for x in nums:\n",
    "            j = bisect_left(g, x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "        return len(g)\n",
    "\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = n\n",
    "        for i in range(n):\n",
    "            sub1 = nums[:i+1]\n",
    "            sub2 = nums[i:].copy()\n",
    "            sub2.reverse()\n",
    "            l1 = self.LIS(sub1)\n",
    "            l2 = self.LIS(sub2)\n",
    "            if l1 > 1 and l2 > 1:\n",
    "                ans = min(ans, n - (l1 + l2 - 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        # import math\n",
    "        # def binary_search(length_min, num):\n",
    "        #     if num > length_min[-1]:\n",
    "        #         length_min.append(num)\n",
    "        #         return len(length_min)-1, length_min\n",
    "        #     if num <= length_min[1]:\n",
    "        #         length_min[1] = num\n",
    "        #         return -n, length_min\n",
    "        #     left = 0\n",
    "        #     right = len(length_min) - 1\n",
    "        #     while(left < right):\n",
    "        #         cur = math.ceil((left + right) / 2)\n",
    "        #         if length_min[cur] < num:\n",
    "        #             left = cur\n",
    "        #         else:\n",
    "        #             right = cur - 1\n",
    "        #     length_min[left+1] = num\n",
    "        #     return left+1, length_min\n",
    "\n",
    "        def insert(length_min, length, num):\n",
    "            if length == len(length_min):\n",
    "                length_min.append(num)\n",
    "            else:\n",
    "                length_min[length] = num\n",
    "            return length_min\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0]*n\n",
    "        length_minf, length_minb  = [], []\n",
    "        for i in range(n):\n",
    "            lengthf = bisect_left(length_minf, nums[i])\n",
    "            length_minf = insert(length_minf, lengthf, nums[i])\n",
    "            dp[i] += lengthf if lengthf != 0 else -n\n",
    "            lengthb = bisect_left(length_minb, nums[n-1-i])\n",
    "            length_minb = insert(length_minb, lengthb, nums[n-1-i])\n",
    "            dp[n-1-i] += lengthb if lengthb != 0 else -n\n",
    "        \n",
    "        return n-max(dp)-1\n",
    "\n",
    "        # n = len(nums)\n",
    "        # dpf = [i for i in range(n)]\n",
    "        # for i in range(1,n):\n",
    "        #     j = i-1\n",
    "        #     while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "        #         j -= 1\n",
    "        # #print(dpf)\n",
    "        # dpb = [i for i in range(n-1,-1,-1)]\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     j = i+1\n",
    "        #     while(j < n and dpb[i] > (j-i-1)):\n",
    "        #         if nums[j] < nums[i]:\n",
    "        #             dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "        #         j += 1\n",
    "        # #print(dpb)\n",
    "        # res = n\n",
    "        # for i in range(1,n-1):\n",
    "        #     if dpf[i] != i and dpb[i] != n-1-i:\n",
    "        #         res = min(res, dpf[i]+dpb[i])\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        incre = [1]*(n)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    incre[i] = max(incre[i], incre[j]+1)\n",
    "        print(incre)\n",
    "        decre = [1]*n\n",
    "        res = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,i,-1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    decre[i] = max(decre[i], decre[j]+1)\n",
    "        \n",
    "        for i in range(1,n-1):\n",
    "            if incre[i]!=1  and decre[i]!=1:\n",
    "                res = max(res, decre[i]+incre[i]-1)\n",
    "        \n",
    "        return n-res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        nums2 = nums.copy()\n",
    "        numset = set(nums2)\n",
    "        uniqnums = list(numset)\n",
    "        uniqnums.sort()\n",
    "        lenu = len(uniqnums)\n",
    "        lenn = len(nums)\n",
    "        numdict = {uniqnums[i]: i for i in range(lenu)}\n",
    "        dp = [[1, 0, 0] for _ in range(lenn+1)]\n",
    "        ans = 0\n",
    "        for i in range(lenn):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    dp[i][1] = max(dp[i][1], max(dp[j][0], dp[j][1])+1)\n",
    "                elif nums[i] < nums[j]:\n",
    "                    if dp[j][1]:\n",
    "                        dp[i][2] = max(dp[i][2], dp[j][1]+1)\n",
    "                    if dp[j][2]:\n",
    "                        dp[i][2] = max(dp[i][2], dp[j][2]+1)\n",
    "                    ans = max(ans, dp[i][2])\n",
    "        # print(dp)\n",
    "        return lenn-ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def f(a):\n",
    "            g = []\n",
    "            ans = 0\n",
    "            for x in a:\n",
    "                idx = bisect_left(g,x)\n",
    "                if idx == len(g):\n",
    "                    g.append(x)\n",
    "                else:\n",
    "                    g[idx] = x\n",
    "                ans = idx + 1\n",
    "            return ans\n",
    "        ans = n\n",
    "        for i in range(1,n - 1):\n",
    "            a,b = f(nums[:i + 1]),f(nums[i:][::-1])\n",
    "            # print(a,b)\n",
    "            if a > 1 and b > 1:\n",
    "                ans = min(ans,n - (a + b - 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            if nums[i] < nums[i+1]:\n",
    "                break\n",
    "            i += 1\n",
    "        for j in range(n-1,0,-1):\n",
    "            if nums[j] < nums[j-1]:\n",
    "                break\n",
    "            j -= 1\n",
    "        nums = nums[i:j+1]\n",
    "        cut = i+n-1-j\n",
    "        n = len(nums)\n",
    "\n",
    "        dpf = [i for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            j = i-1\n",
    "            while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "                j -= 1\n",
    "        #print(dpf)\n",
    "        dpb = [i for i in range(n-1,-1,-1)]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            j = i+1\n",
    "            while(j < n and dpb[i] > (j-i-1)):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "                j += 1\n",
    "        #print(dpb)\n",
    "        res = n\n",
    "        for i in range(1,n-1):\n",
    "            #if dpf[i] != i and dpb[i] != n-1-i:\n",
    "            res = min(res, dpf[i]+dpb[i])\n",
    "        res += cut\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def LIS(self, nums):\n",
    "        lis, g = [], []\n",
    "        for x in nums:\n",
    "            j = bisect_left(g, x)\n",
    "            lis.append(j + 1)\n",
    "            if j == len(g):  # 在 g 的末尾添加元素\n",
    "                g.append(x)\n",
    "            else:  # 修改元素\n",
    "                g[j] = x\n",
    "        return lis\n",
    "    \n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        forward = self.LIS(nums)  # 从左到右的最长递增子序列\n",
    "        backward = self.LIS(nums[::-1])[::-1]  # 从右到左的最长递增子序列\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if forward[i] > 1 and backward[i] > 1:\n",
    "                res = max(res, forward[i] + backward[i] - 1)\n",
    "        return n - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dpf = [i for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            j = i-1\n",
    "            while(j >= 0 and dpf[i] > (i-j-1)):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "                j -= 1\n",
    "        \n",
    "        dpb = [i for i in range(n-1,-1,-1)]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            j = i+1\n",
    "            while(j < n and dpb[i] > (j-i-1)):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "                j += 1\n",
    "        \n",
    "        res = n\n",
    "        for i in range(1,n-1):\n",
    "            if dpf[i] != i and dpb[i] != n-1-i:\n",
    "                res = min(res, dpf[i]+dpb[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        g = []\n",
    "        left = []\n",
    "\n",
    "        for x in nums:\n",
    "            i = bisect_left(g,x)\n",
    "            if i==len(g):\n",
    "                g.append(x)\n",
    "                left.append(len(g)-1)\n",
    "            else:\n",
    "                g[i] =x\n",
    "                left.append(i)\n",
    "        f = []\n",
    "        right = []\n",
    "        for x in nums[::-1]:\n",
    "            i = bisect_left(f,x)\n",
    "            if i==len(f):\n",
    "                f.append(x)\n",
    "                right.append(len(f)-1)\n",
    "            else:\n",
    "                f[i] =x\n",
    "                right.append(i)\n",
    "        right = right[::-1]\n",
    "\n",
    "        res = 0\n",
    "        print(left)\n",
    "        print(right)\n",
    "        for i,j in zip(left,right):\n",
    "            if i and j: # 不能选最大值或者最小值当山顶，不然它在边边不符合题目要求\n",
    "                res = max(i+j+1,res)\n",
    "        return len(nums)-res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums) -> int:\n",
    "        m=len(nums)\n",
    "        for A in range(1,len(nums)-1):\n",
    "            S=list()\n",
    "            for i in range(A):\n",
    "                if nums[i]<nums[A]:\n",
    "                    if S==[] or nums[i]>S[-1]:\n",
    "                        S.append(nums[i])\n",
    "                    elif nums[i]<S[-1]:\n",
    "                        left,right=-1,len(S)-1\n",
    "                        mid=None\n",
    "                        while right-left>1:\n",
    "                            mid=(right+left)//2\n",
    "                            if S[mid]<nums[i]:\n",
    "                                left=mid\n",
    "                            elif  S[mid]>nums[i]:\n",
    "                                right=mid\n",
    "                            else:\n",
    "                                break\n",
    "                        if mid==None or S[mid]!=nums[i]:\n",
    "                            S[right]=nums[i]\n",
    "            if len(S)==0:\n",
    "                continue\n",
    "            S1=list()\n",
    "            for i in range(A+1,len(nums)):\n",
    "                if nums[i]<nums[A]:\n",
    "                    if S1==[] or nums[i]<S1[-1]:\n",
    "                        S1.append(nums[i])\n",
    "                    elif nums[i]>S1[-1]:\n",
    "                        left,right=-1,len(S1)-1\n",
    "                        mid=None\n",
    "                        while right-left>1:\n",
    "                            mid=(right+left)//2\n",
    "                            if S1[mid]>nums[i]:\n",
    "                                left=mid\n",
    "                            elif  S1[mid]<nums[i]:\n",
    "                                right=mid\n",
    "                            else:\n",
    "                                break\n",
    "                        if mid==None or S1[mid]!=nums[i]:\n",
    "                            S1[right]=nums[i]\n",
    "            if len(S1)==0:\n",
    "                continue\n",
    "            m=min(m,len(nums)-(len(S1)+len(S)+1))\n",
    "        return m\n",
    "s=Solution()\n",
    "ans=s.minimumMountainRemovals( [2,1,1,5,6,2,3,1])\n",
    "print(ans)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dpf = [i for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            j = i-1\n",
    "            while(j >= 0):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dpf[i] = min(dpf[i], dpf[j]+(i-j-1))\n",
    "                j -= 1\n",
    "        #print(dpf)\n",
    "        dpb = [i for i in range(n-1,-1,-1)]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            j = i+1\n",
    "            while(j < n):\n",
    "                if nums[j] < nums[i]:\n",
    "                    dpb[i] = min(dpb[i], dpb[j]+(j-i-1))\n",
    "                j += 1\n",
    "        #print(dpb)\n",
    "        res = n\n",
    "        for i in range(1,n-1):\n",
    "            if dpf[i] != i and dpb[i] != n-1-i:\n",
    "                res = min(res, dpf[i]+dpb[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = [1] * n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    left[i] = max(left[i], left[j] + 1)\n",
    "        \n",
    "        right = [1] * n\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(n - 1, i, -1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    right[i] = max(right[i], right[j] + 1)\n",
    "        print(left)\n",
    "        print(right)\n",
    "        ans = n \n",
    "        for i in range(n):\n",
    "            if right[i] > 1 and left[i] > 1:\n",
    "                ans = min(ans, n - right[i] - left[i] + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        minDelete = inf\n",
    "        def minleft(i,leftdelete):\n",
    "            if nums[i-1] >= nums[i]:\n",
    "                m = 1\n",
    "                min_x = inf\n",
    "                for j in range(i-2,-1,-1):\n",
    "                    m += 1\n",
    "                    if nums[j] < nums[i]:\n",
    "                        if min_x > m + leftdelete[j] - 1:\n",
    "                            min_x = m + leftdelete[j] - 1\n",
    "                return min(min_x,m)\n",
    "            else: \n",
    "                min_x = leftdelete[i - 1]\n",
    "                for j in range(i-2,-1,-1):\n",
    "                    if nums[j] >= nums[i]:\n",
    "                        continue\n",
    "                    if min_x > leftdelete[j] + i - j - 1:\n",
    "                        min_x = leftdelete[j] + i - j - 1\n",
    "                return min_x\n",
    "        \n",
    "        def minright(i,rightdelete):\n",
    "            if nums[i+1] >= nums[i]:\n",
    "                m = 1\n",
    "                min_x = inf\n",
    "                for j in range(i+2,len(nums)):\n",
    "                    m += 1\n",
    "                    if nums[j] < nums[i]:\n",
    "                        if min_x > m + rightdelete[j] - 1:\n",
    "                            min_x = m + rightdelete[j] - 1 \n",
    "                return min(m,min_x)\n",
    "            else: \n",
    "                min_x = rightdelete[i+1]\n",
    "                for j in range(i+2,len(nums)):\n",
    "                    if nums[j] >= nums[i]:\n",
    "                        continue\n",
    "                    if min_x > rightdelete[j] + j - i - 1:\n",
    "                        min_x = rightdelete[j] + j - i - 1\n",
    "                return min_x\n",
    "\n",
    "        minDelete = inf\n",
    "        leftdelete = [inf for i in range(len(nums))]\n",
    "        rightdelete = [inf for i in range(len(nums))]\n",
    "        leftdelete[0] = 0\n",
    "        rightdelete[len(nums)-1] = 0\n",
    "        for i in range(1,len(nums)-1):\n",
    "            left = minleft(i,leftdelete)\n",
    "            leftdelete[i] = left\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            right = minright(i,rightdelete)\n",
    "            rightdelete[i] = right\n",
    "        min_i = 0\n",
    "        for i in range(1,len(nums)-1):\n",
    "            delete = leftdelete[i] + rightdelete[i]\n",
    "            if i == leftdelete[i] or len(nums) - i - 1 == rightdelete[i] :\n",
    "                continue\n",
    "            if minDelete > delete:\n",
    "                min_i = i\n",
    "                minDelete = delete\n",
    "        print(leftdelete)\n",
    "        print(rightdelete)\n",
    "        return minDelete\n",
    "    # def minimumMountainRemovals(self,nums):\n",
    "    #     n = len(nums)\n",
    "    #     # 最长递增子序列的长度\n",
    "    #     lis = [1] * n\n",
    "    #     # 最长递减子序列的长度\n",
    "    #     lds = [1] * n\n",
    "        \n",
    "    #     # 计算 lis\n",
    "    #     for i in range(n):\n",
    "    #         for j in range(i):\n",
    "    #             if nums[i] > nums[j]:\n",
    "    #                 lis[i] = max(lis[i], lis[j] + 1)\n",
    "        \n",
    "    #     # 计算 lds\n",
    "    #     for i in range(n - 1, -1, -1):\n",
    "    #         for j in range(n - 1, i, -1):\n",
    "    #             if nums[i] > nums[j]:\n",
    "    #                 lds[i] = max(lds[i], lds[j] + 1)\n",
    "        \n",
    "    #     # 找到最大的 lis + lds - 1\n",
    "    #     max_length = 0\n",
    "    #     for i in range(1, n - 1):\n",
    "    #         if lis[i] > 1 and lds[i] > 1:  # 保证山顶两边都至少有一个元素\n",
    "    #             max_length = max(max_length, lis[i] + lds[i] - 1)\n",
    "        \n",
    "    #     # 总长度减去最大的 lis + lds - 1 即为最小删除次数\n",
    "    #     return n - max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre= [1]*(n+1)\n",
    "        for i in range(n):\n",
    "            for j in range(0,i):\n",
    "                if nums[j]<nums[i]:\n",
    "                    pre[i]=max(pre[i],pre[j]+1)\n",
    "        \n",
    "        suf= [1]*(n+1)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(n-1,i,-1):\n",
    "                if nums[j]<nums[i]:\n",
    "                    suf[i]=max(suf[i],suf[j]+1)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1,n-1):\n",
    "           if suf[i]>1 and pre[i]>1:\n",
    "              ans = max(suf[i]+pre[i]-1,ans)\n",
    "        print(suf)\n",
    "        print(pre)\n",
    "        return n-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        minDelete = inf\n",
    "        def minleft(i,leftdelete):\n",
    "            if nums[i-1] >= nums[i]:\n",
    "                m = 1\n",
    "                min_x = inf\n",
    "                for j in range(i-2,-1,-1):\n",
    "                    m += 1\n",
    "                    if nums[j] < nums[i]:\n",
    "                        if min_x > m + leftdelete[j] - 1:\n",
    "                            min_x = m + leftdelete[j] - 1\n",
    "                return min(min_x,m)\n",
    "            else: \n",
    "                min_x = leftdelete[i - 1]\n",
    "                for j in range(i-2,-1,-1):\n",
    "                    if nums[j] >= nums[i]:\n",
    "                        continue\n",
    "                    if min_x > leftdelete[j] + i - j - 1:\n",
    "                        min_x = leftdelete[j] + i - j - 1\n",
    "                return min_x\n",
    "        \n",
    "        def minright(i,rightdelete):\n",
    "            if nums[i+1] >= nums[i]:\n",
    "                m = 1\n",
    "                min_x = inf\n",
    "                for j in range(i+2,len(nums)):\n",
    "                    m += 1\n",
    "                    if nums[j] < nums[i]:\n",
    "                        if min_x > m + rightdelete[j] - 1:\n",
    "                            min_x = m + rightdelete[j] - 1 \n",
    "                return min(m,min_x)\n",
    "            else: \n",
    "                min_x = rightdelete[i+1]\n",
    "                for j in range(i+2,len(nums)):\n",
    "                    if nums[j] >= nums[i]:\n",
    "                        continue\n",
    "                    if min_x > rightdelete[j] + j - i - 1:\n",
    "                        min_x = rightdelete[j] + j - i - 1\n",
    "                return min_x\n",
    "\n",
    "        minDelete = inf\n",
    "        leftdelete = [inf for i in range(len(nums))]\n",
    "        rightdelete = [inf for i in range(len(nums))]\n",
    "        leftdelete[0] = 0\n",
    "        rightdelete[len(nums)-1] = 0\n",
    "        for i in range(1,len(nums)-1):\n",
    "            left = minleft(i,leftdelete)\n",
    "            leftdelete[i] = left\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            right = minright(i,rightdelete)\n",
    "            rightdelete[i] = right\n",
    "        min_i = 0\n",
    "        for i in range(1,len(nums)-1):\n",
    "            delete = leftdelete[i] + rightdelete[i]\n",
    "            if i == leftdelete[i] or len(nums) - i - 1 == rightdelete[i] :\n",
    "                continue\n",
    "            if minDelete > delete:\n",
    "                min_i = i\n",
    "                minDelete = delete\n",
    "        print(leftdelete)\n",
    "        print(rightdelete)\n",
    "        return minDelete\n",
    "    # def minimumMountainRemovals(self,nums):\n",
    "    #     n = len(nums)\n",
    "    #     # 最长递增子序列的长度\n",
    "    #     lis = [1] * n\n",
    "    #     # 最长递减子序列的长度\n",
    "    #     lds = [1] * n\n",
    "        \n",
    "    #     # 计算 lis\n",
    "    #     for i in range(n):\n",
    "    #         for j in range(i):\n",
    "    #             if nums[i] > nums[j]:\n",
    "    #                 lis[i] = max(lis[i], lis[j] + 1)\n",
    "        \n",
    "    #     # 计算 lds\n",
    "    #     for i in range(n - 1, -1, -1):\n",
    "    #         for j in range(n - 1, i, -1):\n",
    "    #             if nums[i] > nums[j]:\n",
    "    #                 lds[i] = max(lds[i], lds[j] + 1)\n",
    "        \n",
    "    #     # 找到最大的 lis + lds - 1\n",
    "    #     max_length = 0\n",
    "    #     for i in range(1, n - 1):\n",
    "    #         if lis[i] > 1 and lds[i] > 1:  # 保证山顶两边都至少有一个元素\n",
    "    #             max_length = max(max_length, lis[i] + lds[i] - 1)\n",
    "        \n",
    "    #     # 总长度减去最大的 lis + lds - 1 即为最小删除次数\n",
    "    #     return n - max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        g = []\n",
    "        left = []\n",
    "\n",
    "        for x in nums:\n",
    "            i = bisect_left(g,x)\n",
    "            if i==len(g):\n",
    "                g.append(x)\n",
    "                left.append(len(g)-1)\n",
    "            else:\n",
    "                g[i] =x\n",
    "                left.append(i)\n",
    "        f = []\n",
    "        right = []\n",
    "        for x in nums[::-1]:\n",
    "            i = bisect_left(f,x)\n",
    "            if i==len(f):\n",
    "                f.append(x)\n",
    "                right.append(len(f)-1)\n",
    "            else:\n",
    "                f[i] =x\n",
    "                right.append(i)\n",
    "        right = right[::-1]\n",
    "\n",
    "        res = 0\n",
    "        print(left)\n",
    "        print(right)\n",
    "        for i,j in zip(left,right):\n",
    "            if i and j: # 不能选0\n",
    "                res = max(i+j+1,res)\n",
    "        return len(nums)-res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        nums2 = nums.copy()\n",
    "        numset = set(nums2)\n",
    "        lenn = len(nums)\n",
    "        dp = [[1, 0, 0] for _ in range(lenn+1)]\n",
    "        ans = 0\n",
    "        for i in range(lenn):\n",
    "            for j in range(i):\n",
    "                if nums[i] > nums[j]:\n",
    "                    dp[i][1] = max(dp[i][1], max(dp[j][0], dp[j][1])+1)\n",
    "                elif nums[i] < nums[j]:\n",
    "                    if dp[j][1]:\n",
    "                        dp[i][2] = max(dp[i][2], dp[j][1]+1)\n",
    "                    if dp[j][2]:\n",
    "                        dp[i][2] = max(dp[i][2], dp[j][2]+1)\n",
    "                    ans = max(ans, dp[i][2])\n",
    "        return lenn-ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        def longestObstacleCourseAtEachPosition(obstacles: List[int]) -> List[int]:\n",
    "            d = list()\n",
    "            ans = list()\n",
    "            for ob in obstacles:\n",
    "                if not d or ob > d[-1]:\n",
    "                    d.append(ob)\n",
    "                    ans.append(len(d)-1)\n",
    "                else:\n",
    "                    loc = bisect_left(d, ob)\n",
    "                    ans.append(loc)\n",
    "                    d[loc] = ob\n",
    "            return ans\n",
    "        n = len(nums)\n",
    "        forward = longestObstacleCourseAtEachPosition(nums)\n",
    "        nums.reverse()\n",
    "        max_length = 0\n",
    "        backward =longestObstacleCourseAtEachPosition(nums)\n",
    "        print(forward,backward)\n",
    "        for i in range(1,n-1):\n",
    "            if forward[i] and backward[n-1-i]:\n",
    "                max_length = max(forward[i]+backward[n-i-1],max_length)\n",
    "        return n - max_length-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dpl=[0]*n\n",
    "        dpr=[0]*n\n",
    "        res=n\n",
    "        for i in range(n):\n",
    "            dpl[i]=i\n",
    "            for j in range(1,i+1):\n",
    "                if nums[i-j]<nums[i]:\n",
    "                    dpl[i]=min(dpl[i],dpl[i-j]+j-1)\n",
    "        for i in range(n):\n",
    "            dpr[n-1-i]=i\n",
    "            for j in range(1,i+1):\n",
    "                if nums[n-1-i+j]<nums[n-1-i]:\n",
    "                    dpr[n-1-i]=min(dpr[n-1-i],dpr[n-1-i+j]+j-1)\n",
    "        for i in range(1,n-1):\n",
    "            if i!=dpl[i] and dpr[i]!=n-1-i:\n",
    "                res=min(res,dpl[i]+dpr[i])\n",
    "        print(dpl)\n",
    "        print(dpr)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList \n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ##需要计算两个方向上的最长上升子序列\n",
    "        def longestup(obstacles: List[int]) -> List[int]:\n",
    "            ans = []\n",
    "            g = [] #长度为i的序列的最小障碍\n",
    "            for x in obstacles:\n",
    "                j = bisect_left(g,x) \n",
    "                if j == len(g):\n",
    "                    g.append(x)\n",
    "                else:\n",
    "                    g[j] = x\n",
    "                ans.append(j+1)\n",
    "            return ans\n",
    "        left=longestup(nums)\n",
    "        right=longestup(nums[::-1])\n",
    "        right=right[::-1]\n",
    "        # print(left,left)\n",
    "        ans=inf\n",
    "        for i in range(n):\n",
    "            if left[i]>=2 and right[i]>=2:\n",
    "                ans=min(ans,n-left[i]-right[i]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList \n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ##需要计算两个方向上的最长上升子序列\n",
    "        def longestup(obstacles: List[int]) -> List[int]:\n",
    "            ans = []\n",
    "            g = [] #长度为i的序列的最小障碍\n",
    "            for x in obstacles:\n",
    "                j = bisect_left(g,x) \n",
    "                if j == len(g):\n",
    "                    g.append(x)\n",
    "                else:\n",
    "                    g[j] = x\n",
    "                ans.append(j+1)\n",
    "            return ans\n",
    "        left=longestup(nums)\n",
    "        right=longestup(nums[::-1])\n",
    "        right=right[::-1]\n",
    "        print(left,left)\n",
    "        ans=inf\n",
    "        for i in range(n):\n",
    "            if left[i]>=2 and right[i]>=2:\n",
    "                ans=min(ans,n-left[i]-right[i]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs_up(i):\n",
    "            res = 0\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    res = max(res, dfs_up(j))\n",
    "            return res + 1\n",
    "\n",
    "        @cache\n",
    "        def dfs_down(i):\n",
    "            res = 0\n",
    "            for j in range(len(nums) - 1, i, -1):\n",
    "                if nums[j] < nums[i]:\n",
    "                    res = max(res, dfs_down(j))\n",
    "            return res + 1\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums) - 1):\n",
    "            if dfs_up(i) > 1 and dfs_down(i) > 1:\n",
    "                ans = max(dfs_up(i) + dfs_down(i) - 1, ans)\n",
    "        return len(nums) - ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMountainRemovals(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs_up(i):\n",
    "            maxj = 0\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    maxj = max(maxj, dfs_up(j))\n",
    "            return maxj + 1\n",
    "\n",
    "        @cache\n",
    "        def dfs_down(i):\n",
    "            maxj = 0\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[j] < nums[i]:\n",
    "                    maxj = max(maxj, dfs_down(j))\n",
    "            return maxj + 1\n",
    "\n",
    "        return n - max(dfs_up(i) + dfs_down(i) for i in range(1, n - 1) if dfs_up(i) > 1 and dfs_down(i) > 1) + 1\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
